/**
		TRABALHO 2 DA DISCIPLINA SSC0143-PROGRAMACAO CONCORRENTE

		Jhonata Pereira Martins          7656637           
		Normandis Jose Santos Jr.        7656540
		Rafael Araujo de Oliveira        7704971  


							VERSAO PARALELA COM MPI

*/


#include <stdio.h>
#include <limits.h>
#include <mpi.h>

#define N 1000
#define INF INT_MAX

//matriz de adjacencia
int graph[N][N];


int matriz_minimos[N][N];

//funcao para procurar o vertice com a minima distancia do vertice src
int mindistance(int src, int n, int *visitados, int *dist)
{
	int min = INF, min_index;
	int v;
	for (v = 0; v < n; v++)
	{	
		if (visitados[v] == 0 && dist[v] <= min)
		{
			min = dist[v];
			min_index = v;
		}
	}
	return min_index;
}


//implementacao de dijkstra para encontrar o menor caminho entre o vertice src e todos os outros vertices
//retorna um int que eh o valor da maior distancia a partir do vertice src, para facilitar no calculo da menor
//das maximas distancias
int dijkstra(int src, int n)
{

	int i;
	int max = 0;
    int visitados[n];   
    /*
    	nessa abordagem utiliza um vetor de distancias local ao inves de utilizar
		uma matriz de distancias global, para com isso diminuir a comunicação entre os processos
      */      
	int dist[n];
	//inicializa os visitados e as distancias
	for (i = 0; i < n; i++)
	{
		dist[i] = INF;
		visitados[i] = 0;
	}

	//distancia do vertice src eh zero, por ser o vertice de partida
	dist[src] = 0;

	int count;
	int v;
	// encontra o menor caminho de src para todos os vertices
	for (count = 0; count < n-1; count++)
	{
		//escolhe o vertice com a minima distancia. Na primeira iteracao eh sempre o vertice src
		int u = mindistance(src, n, visitados, dist);

		//marca o vertice como visitado
		visitados[u] = 1;
		//Atualiza o valor na matriz de distancias dos vértices adjacentes do vértice escolhido.
		for (v = 0; v < n; v++)
		{			
			if (!visitados[v] && graph[u][v] && dist[u] != INF && dist[u]+graph[u][v] < dist[v])
			{
				dist[v] = dist[u] + graph[u][v];
			}
		}
	}

	//calcula a maior distancia a partir do vertice src	
	for (v = 0; v < n; v++)
	{
		if(dist[v] > max)
		{
			max = dist[v];
		}
	} 
	return max;

}

//inicializa a matriz de adjacencia
void init(int n)                       
{
	int i, j;
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < n; j++)
		{
			graph[i][j] = 0;
		}
	}
}


int main(int argc, char *argv[])
{
	int n, m, a, b, rest;
	int myrank, P, de, ate, i, j, k;

	MPI_Status status;

	MPI_Init (&argc, &argv);
	//diz qm eh cada processo
	MPI_Comm_rank(MPI_COMM_WORLD, &myrank);	
	//diz o numero de processos
	MPI_Comm_size(MPI_COMM_WORLD, &P); 

	//apenas o processo 0 ira fazer a leitura dos dados e distribuir 
	//os buffers de dados para os outros processos
	if(myrank == 0)
	{
		scanf("%d %d ", &n, &m);
		init(n);

		for(i = 0; i < m; i++)
		{
			scanf("%d %d ", &a, &b);
			scanf("%d ", &graph[a-1][b-1]);
			graph[b-1][a-1] = graph[a-1][b-1];
		}

		rest = 0;
		if(n%(P-1))
			rest = 1;
		for(i = 1; i < P; i++)
		{
			//se houver resto de n pelo numero de processos
			//adiciona um vertice a mais para cada processo
			if(rest)
			{
				if(i == 1)
					de = (i-1) * n/(P-1);
				else
					de = ((i-1) * n/(P-1)) + 1;	
				ate = ((i) * n/(P-1)) + 1;
			}
			else
			{
				de = (i-1) * n/(P-1);
				ate = (i) * n/(P-1);
			}
			//enviando para cada processo os dados
			MPI_Send(&n, 1, MPI_INT, i, 1, MPI_COMM_WORLD);
			MPI_Send(graph, n*n, MPI_INT, i, 1, MPI_COMM_WORLD);
			MPI_Send(&de, 1, MPI_INT, i, 1, MPI_COMM_WORLD);
			MPI_Send(&ate, 1, MPI_INT, i, 1, MPI_COMM_WORLD);
		}
		int menor = INF, max;
		//recebendo de cada processo o menor maximo do vertices processados
		for(i = 1; i < P; i++)
		{
			MPI_Recv(&max, 1, MPI_INT, i, 2, MPI_COMM_WORLD, &status);
			if(max < menor)
			{
				menor = max;
			}
		}

		//resposta
		printf("%d\n", menor);	

	}
	else
	{
		//recebendo os dados
		MPI_Recv(&n, 1, MPI_INT, 0, 1, MPI_COMM_WORLD, &status);
		MPI_Recv(graph, n*n, MPI_INT, 0, 1, MPI_COMM_WORLD, &status);
		MPI_Recv(&de, 1, MPI_INT, 0, 1, MPI_COMM_WORLD, &status);
		MPI_Recv(&ate, 1, MPI_INT, 0, 1, MPI_COMM_WORLD, &status);
		int menor = INF;
		// de = (myrank-1) * n/(P-1);
		// ate = (myrank) * n/(P-1);
		for(i = de; i < ate; i++)
		{
			m = dijkstra(i, n);
			if(m < menor)
				menor = m;
		}
		//enviando o menor maximo do processamento dos vertices acima
		MPI_Send(&menor, 1, MPI_INT, 0, 2, MPI_COMM_WORLD);
	}  

	MPI_Finalize();
	return 0;
}
